Skip to main content

square-root

id: square-root title: Square Root sidebar_label: Square-Root tags:

  • Math
  • Binary Search description: "This document provides solutions to the problem of finding the Square Root of an integer."

Problem​

Given an integer x, find the square root of x. If x is not a perfect square, then return the floor value of √x.

Examples​

Example 1:

Input: x = 5
Output: 2
Explanation: Since 5 is not a perfect square, the floor of the square root of 5 is 2.

Example 2:

Input: x = 4
Output: 2
Explanation: Since 4 is a perfect square, its square root is 2.

Your Task​

You don't need to read input or print anything. The task is to complete the function floorSqrt() which takes x as the input parameter and returns its square root. Note: Try solving the question without using the sqrt function. The value of x ≥ 0.

Expected Time Complexity: O(logN)O(log N) Expected Auxiliary Space: O(1)O(1)

Constraints

  • 1 ≤ x ≤ 10^7

Solution​

Intuition & Approach​

To find the square root of a number without using the built-in sqrt function, we can use binary search. This approach leverages the fact that the square root of x must lie between 0 and x. By repeatedly narrowing down the range using binary search, we can efficiently find the floor value of the square root.

Implementation​

class Solution:
def floorSqrt(self, x: int) -> int:
if x == 0 or x == 1:
return x
start, end = 1, x
ans = 0
while start <= end:
mid = (start + end) // 2
if mid * mid == x:
return mid
if mid * mid < x:
start = mid + 1
ans = mid
else:
end = mid - 1
return ans

Complexity Analysis​

The provided solutions efficiently find the floor value of the square root of a given integer x using binary search. This approach ensures a time complexity of O(logN)andanauxiliaryspacecomplexityofO(log N) and an auxiliary space complexity ofO(1)$. The algorithms are designed to handle large values of x up to 10^7 efficiently without relying on built-in square root functions.

Time Complexity: O(logN)O(log N) Auxiliary Space: O(1)O(1)